Cours 2.11.1 du Mastère de Recherches en Informatique <br />Algorithmes avancés - Nicolas Schabanel <br /> <br />Cours n°4 - Partie C/C <br />Introduction à la programmation semi-définie <br />• De la formulation quadratique d'un problème à la formulation sous forme d'un programme vectoriel <br />• Technique d'arrondi : Couper suivant un hyperplan pour Max-Cut <br />• Une O(n^1/3)-approximation pour le coloriage de graphes 3-colorables <br /> <br />TD n°4 <br />• Tirage d'un vecteur unitaire aléatoire uniforme <br />• Une O(n^1/4)-approximation pour le coloriage de graphes 3-coloriables
